package main

import (
	"fmt"
)

type DoubleNode struct {
	data interface{}
	next *DoubleNode
	pre  *DoubleNode
}

type doubleLinked struct {
	head *DoubleNode
}

func (this *doubleLinked) Empty() bool {
	if this.head == nil {
		return true
	} else {
		return false
	}
}
func (this *doubleLinked) Length() int {
	cur := this.head
	count := 0
	for cur != nil {
		count++
		cur = cur.next
	}
	return count
}

func (this *doubleLinked) Add(data interface{}) {
	// 头部插入
	node := &DoubleNode{data: data}
	node.next = this.head
	this.head = node
}

func (this *doubleLinked) Append(data interface{}) {
	// 尾部插入
	node := &DoubleNode{data: data}
	if this.Empty() {
		this.head = node
	}
	cur := this.head
	for cur.next != nil {
		cur = cur.next
	}
	cur.next = node
	node.pre = cur
}

func (this *doubleLinked) Travel() {
	if this.Empty() {
		return
	}
	cur := this.head
	for cur != nil {
		fmt.Printf("%v  ", cur.data)
		cur = cur.next
	}
}

func (this *doubleLinked) Insert(data interface{}, pos int) {
	node := &DoubleNode{data: data}
	if pos <= 0 {
		this.Add(data)
	} else if pos >= this.Length() {
		this.Append(data)
	} else {
		cur := this.head
		count := 1
		for count < pos {
			count++
			cur = cur.next
		}
		node.next = cur.next
		node.pre = cur
		cur.next = node
		node.next.pre = node
	}
}

func (this *doubleLinked) Remove(data interface{}) {
	cur := this.head

	for cur != nil {
		if cur.data == data {
			if cur.pre == nil {
				this.head = cur.next
				cur.pre = nil
			} else if cur.pre != nil {
				cur.pre.next = cur.next
			}
			if cur.next != nil{
				cur.next.pre = cur.pre
			}
			break
		}else {
			cur = cur.next
		}
	}
}

func main() {
	doubleLinked := doubleLinked{}
	fmt.Println(doubleLinked.Empty())
	fmt.Println(doubleLinked.Length())

	doubleLinked.Add(12)
	doubleLinked.Add("语言")
	fmt.Println(doubleLinked.Length())
	doubleLinked.Travel()
	fmt.Println()

	doubleLinked.Append("小花")
	doubleLinked.Append(32)
	fmt.Println(doubleLinked.Length())
	doubleLinked.Travel()
	fmt.Println()

	doubleLinked.Insert("小明超出", 20)
	doubleLinked.Insert("小明小于0", 0)
	doubleLinked.Insert("小明", 1)
	doubleLinked.Travel()
	fmt.Println()
	doubleLinked.Insert(20, 3)
	doubleLinked.Travel()
	fmt.Println()

	doubleLinked.Remove("小明小于0")
	doubleLinked.Travel()
	fmt.Println()
	doubleLinked.Remove("小花")
	doubleLinked.Travel()
	fmt.Println()
}
